package com.lw.leetcode.back.b;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1593. 拆分字符串使唯一子字符串的数目最大
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/10 21:14
 */
public class MaxUniqueSplit {

    public static void main(String[] args) {
        MaxUniqueSplit test = new MaxUniqueSplit();

        // 5
        String str = "ababccc";

        int i = test.maxUniqueSplit(str);
        System.out.println(i);
    }

    private Map<String, Integer> map = new HashMap<>();
    private int length;
    private int max;

    public int maxUniqueSplit(String s) {
        this.length = s.length();
        find(s, 0);
        return max;
    }

    private void find(String s, int st) {
        if (st == length) {
            max = Math.max(max, map.size());
        }
        for (int i = st + 1; i <= length; i++) {
            if (map.size() + length - i < max) {
                return;
            }
            String v = s.substring(st, i);
            if (map.containsKey(v)) {
                continue;
            }
            map.put(v, 1);
            find(s, i);
            map.remove(v);
        }
    }

}
